package me.yuxiaoyao.util.treeify;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author kerryzhang on 2020/10/19
 */

public class TreeUtil {

    private TreeUtil() {
    }

    /**
     * 转换成树的类(带深度) 默认起始深度为 0
     *
     * @param sourceList
     * @param firstTest
     * @param cls
     * @param test
     * @param <T>
     * @param <R>
     * @return
     */
    public static <T, R extends ITreeDepthChildren<R>> List<R> toTreeDepth(List<T> sourceList,
                                                                           ITreeFirstTest<T> firstTest,
                                                                           Class<R> cls,
                                                                           ITreeParentTest<T> test) {
        return toTreeDepth(sourceList, firstTest, cls, test, DefaultTreeMapper.getInstance(), 0, null);
    }


    public static <T, R extends ITreeDepthChildren<R>> List<R> toTreeDepth(List<T> sourceList,
                                                                           ITreeFirstTest<T> firstTest,
                                                                           Class<R> cls,
                                                                           ITreeParentTest<T> test,
                                                                           Comparator<R> comparable) {
        return toTreeDepth(sourceList, firstTest, cls, test, DefaultTreeMapper.getInstance(), 0, comparable);
    }


    public static <T, R extends ITreeDepthChildren<R>> List<R> toTreeDepth(List<T> sourceList,
                                                                           ITreeFirstTest<T> firstTest,
                                                                           Class<R> cls,
                                                                           ITreeParentTest<T> test,
                                                                           ITreeMapper<T, R> treeMapper) {
        return toTreeDepth(sourceList, firstTest, cls, test, treeMapper, 0, null);
    }

    public static <T, R extends ITreeDepthChildren<R>> List<R> toTreeDepth(List<T> sourceList,
                                                                           ITreeFirstTest<T> firstTest,
                                                                           Class<R> cls,
                                                                           ITreeParentTest<T> test,
                                                                           ITreeMapper<T, R> treeMapper,
                                                                           int firstDepth) {
        return toTreeDepth(sourceList, firstTest, cls, test, treeMapper, firstDepth, null);
    }

    /**
     * 转换成树的类(带深度)
     *
     * @param sourceList 来源列表
     * @param firstTest  判断顶级结点的条件
     * @param cls        返回的类型
     * @param test       判断两个节点是否互为父子关系
     * @param <T>
     * @param <R>
     * @return
     */
    public static <T, R extends ITreeDepthChildren<R>> List<R> toTreeDepth(List<T> sourceList,
                                                                           ITreeFirstTest<T> firstTest,
                                                                           Class<R> cls,
                                                                           ITreeParentTest<T> test,
                                                                           ITreeMapper<T, R> treeMapper,
                                                                           int firstDepth,
                                                                           Comparator<R> comparator) {
        List<R> tree = new ArrayList<>();
        // List<T> firstSourceList = new ArrayList<>();
        List<SortPair<T, R>> firstNodes = new ArrayList<>();

        try {
            // 找到一级节点
            for (T source : sourceList) {
                if (firstTest.isFirstNode(source)) {
                    R target = newInstance(cls, source, treeMapper, firstDepth);
                    //firstSourceList.add(t);
                    //tree.add(result);
                    firstNodes.add(new SortPair<>(source, target));
                }
            }
            if (comparator != null) {
                firstNodes.sort((o1, o2) -> comparator.compare(o1.getTarget(), o2.getTarget()));
            }
            // 添加一级节点
            for (SortPair<T, R> node : firstNodes) {
                tree.add(node.getTarget());
            }
            // next depth
            firstDepth++;
            // 递归遍历子节点
            for (SortPair<T, R> firstNode : firstNodes) {
                recursiveToTreeDepth(firstNode.getTarget(), firstNode.getSource(), sourceList, cls, test, treeMapper, firstDepth, comparator);
            }
            /*for (int i = 0; i < tree.size(); i++) {
                recursiveToTreeDepth(tree.get(i), firstSourceList.get(i), sourceList, cls, test, treeMapper, firstDepth, comparable);
            }*/
            return tree;
        } catch (NoSuchMethodException e) {
            throw new RuntimeException(e.getMessage());
        }
    }

    private static <T, R extends ITreeDepthChildren<R>> void recursiveToTreeDepth(R parent,
                                                                                  T sourceParent,
                                                                                  List<T> sourceList,
                                                                                  Class<R> cls,
                                                                                  ITreeParentTest<T> test,
                                                                                  ITreeMapper<T, R> treeMapper,
                                                                                  int depth,
                                                                                  Comparator<R> comparator) throws NoSuchMethodException {
        for (T node : sourceList) {
            if (test.isParent(sourceParent, node)) {
                R subParent = newInstance(cls, node, treeMapper, depth);
                recursiveToTreeDepth(subParent, node, sourceList, cls, test, treeMapper, depth + 1, comparator);
                if (parent.getChildren() == null) {
                    parent.setChildren(new ArrayList<>());
                }
                parent.getChildren().add(subParent);
            }
            if (comparator != null && parent.getChildren() != null) {
                parent.getChildren().sort(comparator);
            }
        }
    }

    private static <T, R extends ITreeDepthChildren<R>> R newInstance(Class<R> cls, T node, ITreeMapper<T, R> treeMapper, int depth) throws NoSuchMethodException {
        R subParent = ReflectUtil.newInstance(cls);
        treeMapper.mapper(node, subParent);
        subParent.setTreeDepth(depth);
        return subParent;
    }


    /**
     * 转换成树的类
     *
     * @param sourceList 来源列表
     * @param firstTest  判断顶级结点的条件
     * @param cls        返回的类型
     * @param test       判断两个节点是否互为父子关系
     * @param <T>
     * @param <R>
     * @return
     */
    public static <T, R extends ITreeChildren<R>> List<R> toTree(List<T> sourceList,
                                                                 ITreeFirstTest<T> firstTest,
                                                                 Class<R> cls,
                                                                 ITreeParentTest<T> test) {
        return toTree(sourceList, firstTest, cls, test, DefaultTreeMapper.getInstance(), null);
    }

    public static <T, R extends ITreeChildren<R>> List<R> toTree(List<T> sourceList,
                                                                 ITreeFirstTest<T> firstTest,
                                                                 Class<R> cls,
                                                                 ITreeParentTest<T> test,
                                                                 ITreeMapper<T, R> treeMapper) {
        return toTree(sourceList, firstTest, cls, test, treeMapper, null);
    }


    public static <T, R extends ITreeChildren<R>> List<R> toTree(List<T> sourceList,
                                                                 ITreeFirstTest<T> firstTest,
                                                                 Class<R> cls,
                                                                 ITreeParentTest<T> test,
                                                                 Comparator<R> comparator) {
        return toTree(sourceList, firstTest, cls, test, DefaultTreeMapper.getInstance(), comparator);
    }


    public static <T, R extends ITreeChildren<R>> List<R> toTree(List<T> sourceList,
                                                                 ITreeFirstTest<T> firstTest, Class<R> cls,
                                                                 ITreeParentTest<T> test,
                                                                 ITreeMapper<T, R> treeMapper,
                                                                 Comparator<R> comparator) {
        List<R> tree = new ArrayList<>();
        // List<T> firstSourceList = new ArrayList<>();
        List<SortPair<T, R>> firstNodes = new ArrayList<>();
        try {
            // 找到一级节点
            for (T source : sourceList) {
                if (firstTest.isFirstNode(source)) {
                    R target = newInstance(cls, source, treeMapper);
                    //firstSourceList.add(source);
                    //tree.add(target);
                    firstNodes.add(new SortPair<>(source, target));
                }
            }
            if (comparator != null) {
                // delegate 给 comparator
                firstNodes.sort((o1, o2) -> comparator.compare(o1.getTarget(), o2.getTarget()));
            }
            // 添加一级节点
            for (SortPair<T, R> node : firstNodes) {
                tree.add(node.getTarget());
            }
            // 递归遍历子节点
            for (SortPair<T, R> firstNode : firstNodes) {
                recursiveToTree(firstNode.getTarget(), firstNode.getSource(), sourceList, cls, test, treeMapper, comparator);
            }

            // 递归遍历子节点
            /*
            for (int i = 0; i < tree.size(); i++) {
                recursiveToTree(tree.get(i), firstSourceList.get(i), sourceList, cls, test, treeMapper, comparator);
            }
             */
            return tree;
        } catch (NoSuchMethodException e) {
            throw new RuntimeException(e.getMessage());
        }
    }

    private static <T, R extends ITreeChildren<R>> void recursiveToTree(R parent,
                                                                        T sourceParent,
                                                                        List<T> sourceList,
                                                                        Class<R> cls,
                                                                        ITreeParentTest<T> test,
                                                                        ITreeMapper<T, R> treeMapper,
                                                                        Comparator<R> comparator) throws NoSuchMethodException {
        for (T node : sourceList) {
            if (test.isParent(sourceParent, node)) {
                R subParent = newInstance(cls, node, treeMapper);
                recursiveToTree(subParent, node, sourceList, cls, test, treeMapper, comparator);
                if (parent.getChildren() == null) {
                    parent.setChildren(new ArrayList<>());
                }
                parent.getChildren().add(subParent);
            }
            if (comparator != null && parent.getChildren() != null) {
                parent.getChildren().sort(comparator);
            }
        }
    }


    private static <T, R extends ITreeChildren<R>> R newInstance(Class<R> cls, T node, ITreeMapper<T, R> treeMapper) throws NoSuchMethodException {
        R subParent = ReflectUtil.newInstance(cls, node);
        treeMapper.mapper(node, subParent);
        return subParent;
    }

    private static class SortPair<S, T> {
        private final S source;
        private final T target;

        private SortPair(S source, T target) {
            this.source = source;
            this.target = target;
        }

        public S getSource() {
            return source;
        }

        public T getTarget() {
            return target;
        }
    }
}
